The present invention relates to methods and apparatus for signal processing.
State of the art computer vision systems and methods and state of the art associative processing methods are described in the following publications, the disclosure of which is hereby incorporated by reference:
C. C. Foster, xe2x80x9cContent addressable parallel processorsxe2x80x9d, Van Nostrand Reinhold Co., 1976, chs.2 and 5,
S. Ruhman, I. Scherson, xe2x80x9cAssociative processor for tomographic image reconstructionxe2x80x9d, Proc. Medcomp 82 (1982 IEEE Comp Soc. Int. Conf. on Medical Comp. Sc./Computational Medicine), pp. 353-358,
C. Weems, E. Riseman, A. Hanson, A. Rosenfeld, xe2x80x9cIU parallel processing benchmarkxe2x80x9d, Proc. Comp. Vision and Pattern Recogn., pp. 673-688, 1988,
I. Scherson, xe2x80x9cMultioperand associative processing and application to tomography and computer graphicsxe2x80x9d, Ph.D. Thesis, Computer Science, Weizman Institute of Science, 1983,
Canny J., xe2x80x9cComputational approach to edge detectionxe2x80x9d, IEEE Trans. on Pattern Analysis and Machine Int., November 1986, pp. 679-698, and
Sha""ashua, A. and S. Ullman, xe2x80x9cStructural saliency: the detection of global salient structures using a local connected networkxe2x80x9d, Proc. ICCV Conf., pp, 321-327, Florida, 1988, and
Akerib, A. J. and Shmil Ruhman, xe2x80x9cAssociative contour processingxe2x80x9d, MVP 1990 IAPR Workshop on Machine Vision applications, Nov. 28-30, 1990, Tokyo.
Image processing techniques and other subject matter useful for associative signal processing are described in the following references:
[1] W. D. Hillis, xe2x80x9cThe Connection Machinexe2x80x9d, MIT Press, 1985.
[2] C. C. Weems, Jr., xe2x80x9cImage Processing on a Content Addressable Array Parallel Processorxe2x80x9d, Ph.D. Thesis, Computer and Information Sciences, University of Massachusetts at Amherst, 1984.
[3] C. C. Foster, xe2x80x9cContent Addressable Parallel Processorsxe2x80x9d, Van Nostrand Reinhold Co., 1976, chs. 2 and 5.
[4] S. Ruhman, I. Scherson, xe2x80x9cAssociative Processor for Tomographic Image Reconstructionxe2x80x9d, Proc. Medcomp 82 (1982 IEEE Comp. Soc. Int. Conf. on Medical Comp. Sc./Computational Medicine), pp 353-358.
[5] S. Ruhman, I. Scherson, xe2x80x9cFeasibility Study of Associative Radar Signal Processingxe2x80x9d, Internal Report, Weizmann Institute of Science, October 1984.
[6] S. Ruhman, I. Scherson, xe2x80x9cAssociative Processor Particularly Useful for Tomographic Image Reconstructionxe2x80x9d, U.S. Pat. No. 4,491,932, filed Oct. 1, 1981, issued Jan. 1, 1985.
[7] C. Weems, E. Riseman, A. Hanson, A. Rosenfeld, xe2x80x9cIU Parallel Processing Benchmarkxe2x80x9d, Proc. Comp. Vision and Pattern Recogn. pp 673-688, 1988.
[8] D. C. Marr, E. Hildreth, xe2x80x9cTheory of Edge Detectionxe2x80x9d, Proc. R. Soc. London, Vol. B 207, pp 187-217, 1980.
[9] W. E. L. Grimson, xe2x80x9cA Computer Implementation of a Theory of Human Stereo Visionxe2x80x9d, Phil. Trans. Royal Soc. of London, Vol. B 292, pp 217-253, 1981.
[10] B. K. P. Horn, B. G. Schunck, xe2x80x9cDetermining Optical Flowxe2x80x9d, Artificial Intelligence Vol. 17, pp 185-203, 1981.
[11] V. Cantoni, C. Guerra and S. Levialdi, xe2x80x9cTowards an Evaluation of an Image Processing Systemxe2x80x9d. In: Computing Structures for Image Processing, Academic Press, 1983, ch. 4.
[12] M. J. Flynn, xe2x80x9cVery high-speed computer systemsxe2x80x9d, Proc. IEEE, Vol. 54, pp 1901-1909, 1966.
[13] B. Lindskog xe2x80x9cPICAP, An SIMD architecture for multi-dimensional signal processingxe2x80x9d, Dissertation No. 176, Dept. of El. Eng., Linkoping University, Sweden, 1988.
[14] S. S. Wilson, xe2x80x9cOne dimensional SIMD architecturesxe2x80x94the AIS-5000xe2x80x9d, Multicomputer Vision, Academic Press, pp. 131-149.
[15] D. Juvini, J. L. Basille, H. Essafi, J. Y. Latil, xe2x80x9cSympati 2, a 1.5D processor array for image applicationxe2x80x9d, EUSIPCO IV, Theories and applications, North-Holland, pp. 311-314, 1988.
[16] I. N. Robinson and W. R. Moore, xe2x80x9cA parallel processor array architecture and its implementation in siliconxe2x80x9d, Proc. IEEE Custom Integrated Circuit Conf. pp 41-45, 1982.
[17] M. J. B. Duff, xe2x80x9cCLIP4: A large scale integrated circuit array parallel processorxe2x80x9d, Proc. IJCPR, pp. 728-733, 1976.
[18] K. E. Batcher, xe2x80x9cDesign of a massively parallel processorxe2x80x9d, IEEE Trans. Comp., Vol. C-29, pp. 836-840, 1980.
[19] S. F. Reddaway, xe2x80x9cDAPxe2x80x94A flexible number cruncherxe2x80x9d, Proc. LASL Workshop on Vector and Parallel Processors, pp. 233-234, 1978.
[20] D. E. Shaw, xe2x80x9cThe NON-VON supercomputerxe2x80x9d, Computer Science Dept., Columbia University, New York, N.Y., 1982.
[21] V. Cantoni and S. Levialdi, xe2x80x9cPAPIA: A case history,xe2x80x9d, Parallel Computer Vision, L. Uhr, Ed. New York, N.Y.: Academic Press, 1987, pp. 3-13.
[22] L. I. Hungwen and M. Maresca. xe2x80x9cPolymorphic-Torus Architecture for Computer Visionxe2x80x9d, IEEE Trans. PAMI, Vol. 11, No. 3, 1989.
[23] S. R. Sternberg, xe2x80x9cBiomedical image processingxe2x80x9d, Computer, Vol. 16, pp. 22-35, 1983.
[24] E. W. Kent, M. O. Shneier, and R. Lumia, xe2x80x9cPIPE Pipeline image processing enginexe2x80x9d, Parallel and Distributed Computing, Vol. 2, pp. 50-78, 1985.
[25] Max Video product literature, Datacube Corp., Peabody, Mass., 1987.
[26] T. Gross, H. T. Kung, M. S. Lam, and J. A. Webb, xe2x80x9cWarp as a machine for low-level visionxe2x80x9d, Proc. of the 1985 Int. Conf. on Robotics and Automation, 1985.
[27] W. W. Wilcke, R. C. Booth, D. A. Brown, D. G. Shea, and F. T. Tong, xe2x80x9cDesign and application of an experimental multiprocessorxe2x80x9d, IBM RC 12604, 1987.
[28] C. Withby-Strevens, xe2x80x9cThe Transputerxe2x80x9d, Proc. 12th ACM Int. Symp. on Computer Architectures, pp. 292-300, 1985.
[29] L. Erman, xe2x80x9cThe Hearsay-II Speech-Understanding System: integrating knowledge to resolve uncertaintyxe2x80x9d, Computing Surveys Vol. 12, pp. 213-253, 1980.
[30] H. P. Nii, xe2x80x9cThe blackboard model of problem solving and the evaluation of blackboard architecturesxe2x80x9d, AI Magazine, Vol. 7, No. 2, pp. 38-53, 1986.
[31] B. A. Draper, R. T. Collins, J. Brolio, J. Griffith, A. R. Hanson, and E. M. Riseman, xe2x80x9cTools and experiments in the knowledge-directed interpretation of road scenesxe2x80x9d, Proc. Image Understanding Workshop, Morgan Kaufmann: Los Altos, Calif., 1987.
[32] NCube Corp, Promotional literature, Beaverton, Oreg., 1985.
[33] C. Fernstrom, I. Kruzela, B. Svensson, xe2x80x9cLUCAS Associative Array Processorxe2x80x9d, Springer-Verlag, 1985, ch. 2.
[34] S. Ruhman, I. Scherson, xe2x80x9cAssociative Memory Cell and Memory Unit Including Samexe2x80x9d, U.S. Pat. No. 4,404,653, filed Oct. 1, 1981, issued Sep. 13, 1983.
[35] I. Scherson, xe2x80x9cMultioperand Associative Processing and Application to Tomography and Computer Graphicsxe2x80x9d, Ph.D. thesis, Computer Sciences, Weizmann Institute of Science, 1983.
[36] J. Worlton, xe2x80x9cSome Patterns Technology Change in High-Performance Computersxe2x80x9d, Proc. Supercomputing, pp 312-320, November 1988.
[37] I. Scherson, S. Ruhman, xe2x80x9cMulti-Operand Associative Arithmeticxe2x80x9d, Proc. 6th Symp. on Computer Arithmetic, Aarhus 1983, pp 124-128.
[38] I. Scherson, S. Ruhman, xe2x80x9cMulti-Operand Arithmetic in a Partitioned Associative Architecturexe2x80x9d, J. of Parallel and Distr. Comp., Vol. 5., pp 655-668, 1988.
[39] D. C. Marr, E. Hildreth, xe2x80x9cTheory of Edge Detectionxe2x80x9d, Proc. R. Soc. London, Vol. B 207, pp 187-217, 1980.
[40] John Canny, xe2x80x9cComputational Approach to Edge Detectionxe2x80x9d, IEEE Trans. on Pattern Analysis a Machine Int., November 1986, pp. 679-698.
[41] E. R. Davis and A. P. N. Plummer, Thinning Algorithms: A Critique and New Methodology, Pattern Recognition 14: 53-63, 1981.
[42] R. T. Chin, H. K. War, D. L. Stover, and R. D. Iverson, A One-Pass Thinning Algorithm and its Parallel Implementation, Comp. Vision, Graph. and, Image Proc. 40: 30-40, 1987.
[43] W. E. L. Grimson, xe2x80x9cA Computer Implementation of a Theory of Human Stereo Visionxe2x80x9d, Phil. Trans. Royal Soc. of London, Vol. B 292, pp 217-253. 1981.
[44] D. Marr, T. Poggio, xe2x80x9cA Computational Theory of Human Stereo Visionxe2x80x9d, Proc. Royal Soc. London B 204, pp 301-324, 1979.
[45] B. K. P. Horn, B. G. Schunck, Determining Optical Flow, Artificial Intelligence, Vol. 17, pp 185-203, 1981.
[46] Amnon Sha""ashua and Shimon Ullman, xe2x80x9cStructural Saliency: The Detection of Global Salient Structures Using a Local Connected Networkxe2x80x9d, Proc. ICCV Conf., pp. 321-327, Florida, 1988.
[47] Amnon Sha""ashua, xe2x80x9cStructural Saliency: The detection of globally salient structures using a locally connected networkxe2x80x9d, M.Sc thesis, Dept. of Applied Math., Weizmann Inst. of Science, 1988.
[48] Amnon Sha""ashua, AI Lab., MIT, Private Communication, May 1991.
[49] Duda R. O. and Hart P. E., xe2x80x9cUse of the Hough transformation to detect lines and curves in picturesxe2x80x9d, Comm. ACM Vol. 15, Num. 1, pp. 11-15, January 1972.
[50] O""Gorman, F. and M. B. Clowes xe2x80x9cFinding picture edge through collinearity of feature pointsxe2x80x9d, Proc. Int. Joint Conf. on Artif. Intel., pp. 543-55, 1973.
[51] A. Rosenfeld, A. C. Kak, xe2x80x9cDigital Picture Processingxe2x80x9d, Academic Press, 1982.
[52] Robert Sedgewick, xe2x80x9cAlgorithmsxe2x80x9d, Addison-Veslev, 1988.
[53] Preston, K., xe2x80x9cThe Abingdon Cross benchmark surveyxe2x80x9d, IEEE Computer 22(7), pp 9-19, 1989.
[54] S. Siegel and S. Waltings, xe2x80x9cMax Video""s Performance of the Abingdon Cross Bench-Mark, xe2x80x9d, Proc. Vision ""87, Society of Manufacturing Engineers, Dearborn, Mich., pp 2-17, 1987.
[55] W. B. Teeuw and R. P. W. Duin, xe2x80x9cAn algorithm for benchmarking an SIMD pyramid with the Abingdon Crossxe2x80x9d, Pattern Recognition Letters 11, pp 501-506, 1990.
[56] K. Preston Jr., xe2x80x9cBenchmark Resultsxe2x80x94The Abingdon Crossxe2x80x9d, Evaluation of Multicomputers for Image Processing, L. Uhr et al., eds., Academic Press, Cambridge, Mass., 1986.
[57] A. J. Akerib, S. Ruhman, S. Ullman, xe2x80x9cReal Time Associative Vision Machinexe2x80x9d, Proc. 7th Israel Conf. on Artif. Intel., Vision and Pattern Recog. Elsevier, December 1990.
[58] Avidan J. Akerib and Smil Ruhman, xe2x80x9cAssociative Contour Processingxe2x80x9d, MVP""90 IAPR Workshop on Machine Vision Applications, Nov. 28-30, 1990, Tokyo.
[59] Avidan J. Akerib and Smil Ruhman xe2x80x9cAssociative Array and Tree Algorithms in Stereo Visionxe2x80x9d, Proc. 8th Israel Conf..on Artif. Intel. Vision and Pattern Recog., Elsevier, December 1991.
All of the above references and publications cited therein are hereby incorporated by reference. Numbers in square brackets in the text are references to the above documents.
The present invention seeks to provide improved methods and apparatus for signal processing.
The Associative Signal Processing (ASP) approach is now compared to a conventional serial computer""s structure which includes a memory and a CPU. The CPU is responsible for computation, while the memory is a simple device which only stores data.
The ASP architecture is totally different. The computation is carried out on an xe2x80x9cintelligent memoryxe2x80x9d while the CPU is replaced by a simple controller that manages this xe2x80x9cintelligentxe2x80x9d memory. In addition to its capability to read and write, each cell or word in this memory can identify its contents and change it according to instructions received from the controller.
For example, assume an array of a million numbers between 1 and 5. The requirement is to add 3 to the array.
In conventional serial computers, a number is transferred from the addressable memory to the CPU, 3 is then added, and the result is returned to the memory. The process takes 1-3 machine cycles for each specific number, for a total of 1-3 million machine cycles for the whole array.
In the associative approach the one million numbers are stored in the xe2x80x9cintelligent memoryxe2x80x9d. The controller has to ask five questions and generate five answers as follows: xe2x80x9cWho is 5?xe2x80x9d Please identify yourself.xe2x80x9d This takes one machine cycle. The controller instructs all those who identified themselves, to become xe2x80x9c8xe2x80x9d. The controller continues to ask xe2x80x9cWho is 4xe2x80x9d and instruct xe2x80x9cYou are 7!xe2x80x9d and so on, until it covers all the combinations.
This operation takes only 10 machine cycles in comparison to 1-3 million machine cycles with conventional serial computers. Using this basic instruction set of read, identify and write, all the arithmetical and logical operations can be performed.
There is thus provided, in accordance with a preferred embodiment of the present invention, associative signal processing apparatus for processing an incoming signal, the apparatus including an array of processors, each processor including a multiplicity of associative memory cells, each sample of an incoming signal being processed by at least one of the processors a register array including at least one register operative to store responders arriving from the processors and to provide communication between processors, and an I/O buffer register for inputting and outputting a signal, wherein the processor array, the register array and the I/O buffer register are arranged on a single module.
There is also provided, in accordance with a preferred embodiment of the present invention, associative signal processing apparatus including an array of processors, each processor including a multiplicity of associative memory cells, at least one of the processors being operative to process a plurality of samples of an incoming signal, a register array including at least one register operative to store responders arriving from the processors and to provide communication between processors, and an I/O buffer register for inputting and outputting a signal.
Further in accordance with a preferred embodiment of the present invention, the processor array, the register array and the I/O buffer register are arranged on a single chip.
Still further in accordance with a preferred embodiment of the present invention, the register array is operative to perform at least one multicell shift operation.
There is also provided, in accordance with a preferred embodiment of the present invention, signal processing apparatus including an array of associative memory words, each word including a processor, each sample of an incoming signal being processed by at least one of the processors, a register array including at least one register operative to provide communication between words and to perform at least one multicell shift operation, and an I/O buffer register for inputting and outputting a signal.
Further in accordance with a preferred embodiment of the present invention, the register array is also operative to perform single cell shift operations.
Still further in accordance with a preferred embodiment of the present invention, the I/O buffer register and the processors are operative in parallel.
Additionally in accordance with a preferred embodiment of the present invention, the word length of the I/O buffer register is increasable by decreasing the wordlength of the associative memory cells.
Further in accordance with a preferred embodiment of the present invention, the apparatus is operative in video real time.
Still further in accordance with a preferred embodiment of the present invention, the signal includes an image.
Further in accordance with a preferred embodiment of the present invention, at least one word in the array of words includes at least one nonassociative memory cell.
Still further in accordance with a preferred embodiment of the present invention, at least one word in the array of words includes at least one column of nonassociative memory cells.
Further in accordance with a preferred embodiment of the present invention, the array, the register array and the I/O buffer register are arranged on a single module.
Still further in accordance with a preferred embodiment of the present invention, the module has a bus which receives instructions and also performs at least one multicell shift operation.
Additionally in accordance with a preferred embodiment of the present-invention, the module has a first bus which performs at least one multicell shift operation and a second bus which performs at least one single cell shift operation.
There is also provided, in accordance with a preferred embodiment of the present invention, an array of processors which communicate by multicell and single cell shift operations, the array including a plurality of processors, a first bus connecting at least a pair of the processors which is operative to perform at least one multicell shift operation, and a second bus connecting at least a pair of the processors which is operative to perform single cell shift operations.
There is additionally provided, in accordance with a preferred embodiment of the present invention, a signal processing method including:
for each consecutive pair of first and second signal characteristics within a sequence of signal characteristics, counting the number of samples having the first signal characteristic, and
subsequently, counting the number of samples having the second signal characteristic.
Further in accordance with a preferred embodiment of the present invention, counting includes generating a histogram.
Still further in accordance with a preferred embodiment of the present invention, the signal includes a color image.
Still further in accordance with a preferred embodiment of the present invention, at least one characteristic includes at least one of the following group of characteristics: intensity, noise, and color density.
Further in accordance with a preferred embodiment of the present invention, the method also includes scanning a medium bearing the color image.
Still further in accordance with a preferred embodiment of the present invention, the image includes a color image.
There is also provided, in accordance with a preferred embodiment of the present invention, an edge detection method including identifying a first plurality of edge pixels and a second plurality of candidate edge pixels, identifying, in parallel, all candidate edge pixels which are connected to at least one edge pixel as edge pixels, and repeating the second identifying step at least once.
There is additionally provided, in accordance with a preferred embodiment of the present invention, a signal processing method including storing an indication that a first plurality of first samples has a first characteristic, storing, in parallel for all individual samples which are connected to at least one sample having the first characteristic, an indication that the connected samples have the first characteristic, and repeating the second step at least once.
Further in accordance with a preferred embodiment of the present invention, the signal includes an image and the first characteristic of the first samples is that the first samples are edge pixels.
There is also provided, in accordance with a preferred embodiment of the present invention, a feature labeling method in which a signal is inspected, the signal including at least one feature, the feature including a set of connected samples, the method including storing a plurality of indices for a corresponding plurality of samples, replacing, in parallel for each individual sample from among the plurality of samples, the stored index of the individual sample by an index of a sample connected thereto, if the index of the connected sample is ordered above the index of the individual sample, and repeating the replacing step at least once.
Further in accordance with a preferred embodiment of the present invention, replacing is repeated until only a small number of indices are replaced in each iteration.
Still further in accordance with a preferred embodiment of the present invention, the signal includes an image.
Additionally in accordance with a preferred embodiment of the present invention, the signal includes a color image.
Still further in accordance with a preferred embodiment of the present invention, the samples include pixels, the first characteristic includes at least one color component and adjacency of pixels at least partly determines connectivity of samples.
Additionally in accordance with a preferred embodiment of the present invention, the pixels form an image in which a boundary is defined and repeating is performed until the boundary is reached.
Further in accordance with a preferred embodiment of the present invention, repeating is performed a predetermined number of times.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for image correction including computing a transformation for an output image imaged by a distorting lens, such as an HDTV lens, which compensates for the lens distortion, and applying the transformation in parallel to each of a plurality of pixels in the output image.
There is also provided associative signal processing apparatus including a plurality of comparing memory elements each of which is operative to compare the contents of memory elements other than itself to respective references in accordance with a user-selected logical criterion, thereby to generate a responder if the comparing memory element complies with the criterion, and a register operative to store the responders.
Further in accordance with a preferred embodiment of the present invention, the criterion includes at least one logical operand.
Still further in accordance with a preferred embodiment of the present invention, at least one logical operand includes a reference for at least one memory element other than the comparing memory element itself. For example, a plurality of memory elements may be respectively responsible for a corresponding plurality of pixels forming a color image. The references may include three specific pixel values A, B and C and the user-selected logical criterion may be that an individual pixel have a value of A, OR that its upper right neighbor has a value of B and its lower left neighbor has a value of C.
Further in accordance with a preferred embodiment of the present invention, each memory element includes at least one memory cell.
Still further in accordance with a preferred embodiment of the present invention, the plurality of comparing memory elements are operative in parallel to compare the contents of a memory element other than themselves to an individual reference.
There is also provided, in accordance with a preferred embodiment of the present invention, an associative memory including an array of PEs (processor elements) including a plurality of PE""s, wherein each PE includes a processor of variable size, and a word of variable size including an associative memory cell, wherein all of the associative memory cells from among the plurality of associative memory cells included in the plurality of PE""s are arranged in the same location within the word and wherein the plurality of words included in the plurality of PE""s together form a FIFO.
Further in accordance with a preferred embodiment of the present invention, the word of variable size includes more than one associative memory cell.
There is also provided, in accordance with a preferred embodiment of the present invention, a method for modifying contents of a multiplicity of memory cells and including performing, once, an arithmetic computation on an individual value stored in a plurality of memory cells and storing the result of the arithmetic computation in a plurality of memory cells which contain the individual value.
Further in accordance with a preferred embodiment of the present invention, storing is carried out in all memory cells in parallel.
Also described herein is a chip for multimedia and image processing applications. It is suitable for low-cost, low power consumption, small size and high-performance real-time image processing for consumer applications and high-end powerful image processing for multimedia and communication applications.
The chip is a general purpose, massively parallel processing chip, in which typically 1024 associative processors are crowded onto one chip, enabling the processing of 1024 digital words in one machine cycle of the computer clock.
The chip was designed to allow the performance of a wide range of image processing and multimedia applications in real-time video rate. In comparison, existing general purpose, serial computing chips and digital signal processing chips (DSPs) enable the processing of only 1-16 words in one machine cycle.
The chip""s major instruction set is based on four basic commands that enable the performance of all arithmetic and logic instructions. This is another design advantage that allows more than a thousand processors to be crowded onto a single chip.
A single chip typically performs the equivalent of 500-2000 million instructions per second (MIPS). A system based on the chip""s architecture can reach multimedia performance of high-end computers at only a small fraction of the price of typical high-end computers.
The chip is based on a modular architecture, and enables easy connection of more than one chip in order to gain high performance (in a linear ratio). Thus, a large number of the chips can be connected in parallel in order to linearly increase overall performance to the level of the most sophisticated supercomputers.
Existing CPU chips and DSPs require a dedicated operating system when more than one chip is connected in parallel. The performance increases in ratio to the square root of the number of chips connected together. Connecting more than two chips requires the architecture of a supercomputer.
The chip""s architecture allows massively parallel processing in concurrence with data input and output transactions. As an associative processor, each of the 1024 chips has its own internal memory and data path. The chip""s data path architecture provides parallel loading of data into the internal processors, thereby eliminating the bottleneck between memory and CPU that can cause severe performance degradation in serial computers.
The chip uses an average of 1 watt to perform the equivalent of 500 MIPS which is 10-25 times better than existing general purpose and DSP chips.
There is also provided in accordance with another preferred embodiment of the present invention associative signal processing apparatus for processing an incoming signal comprising a plurality of samples, the apparatus including a two-dimensional array of processors, each processor including a multiplicity of content addressable memory cells, each sample of an incoming signal being processed by at least one of the processors, and a register array including at least one register operative to store responders arriving from the processors and to provide communication, within a single cycle, between non-adjacent processors.
There is also provided in accordance with another preferred embodiment of the present invention associative signal processing apparatus including an array of processors, each processor including a multiplicity of associative memory cells, at least one of the processors being operative to process a plurality of samples of an incoming signal, a register array including at least one register operative to store responders arriving from the processors and to provide communication between processors, and an I/O buffer register operative to input an incoming signal and to output an outgoing signal.
Further in accordance with a preferred embodiment of the present invention the processor array, the register array and the I/O buffer register are arranged on a single chip.
Still further in accordance with a preferred embodiment of the present invention the register array is operative to perform at least one multicell shift operation.
Additionally in accordance with a preferred embodiment of the present invention the register array is operative to perform at least one multicell shift operation.
There is also provided in accordance with another preferred embodiment of the present invention associative apparatus including a plurality of comparing memory elements each of which is operative to compare the contents of memory elements other than itself to respective references in accordance with a user-selected logical criterion, thereby to generate a responder if the comparing memory element complies with the criterion, and a register operative to store the responders.
Further in accordance with a preferred embodiment of the present invention the criterion includes at least one logical operand.
Still further in accordance with a preferred embodiment of the present invention the I/O buffer register and the processors are operative in parallel.
Additionally in accordance with a preferred embodiment of the present invention the word length of the I/O buffer register is increasable by decreasing the wordlength of the associative memory cells.
Further in accordance with a preferred embodiment of the present invention the apparatus is operative in video real time.
Still further in accordance with a preferred embodiment of the present invention the signal includes an image.
Additionally in accordance with a preferred embodiment of the present invention the at least one logical operand includes a reference for at least one memory element other than the comparing memory element itself.
Moreover in accordance with a preferred embodiment of the present invention each memory element includes at least one memory cell.
Further in accordance with a preferred embodiment of the present invention the plurality of comparing memory elements are operative in parallel to compare the contents of a memory element other than themselves to an individual reference.
There is also provided in accordance with another preferred embodiment of the present invention a method for image correction including computing a transformation for an output image imaged by a distorting lens which compensates for the lens distortion, and applying the transformation in parallel to each of a plurality of pixels in the output image.
Further in accordance with a preferred embodiment of the present invention the distorting lens includes an HDTV lens.
There is also provided in accordance with a preferred embodiment of the present invention an array of processors which communicate by multicell and single cell shift operations, the array including a plurality of processors, a first bus connecting at least a pair of the processors which bus is operative to perform at least one multicell shift operation, and a second bus connecting at least a pair of the processors which bus is operative to perform single cell shift operations.
There is also provided in accordance with another preferred embodiment of the present invention a signal processing method for processing a signal including for each consecutive pair of first and second signal characteristics within a sequence of signal characteristics, counting in parallel the number of samples having the first signal characteristic, and subsequently, counting in parallel the number of samples having the second signal characteristic.
Further in accordance with a preferred embodiment of the present invention the counting includes generating a histogram.
Still further in accordance with a preferred embodiment of the present invention the signal includes a color image.
Additionally in accordance with a preferred embodiment of the present invention at least one characteristic includes at least one of the following group of characteristics: intensity, noise, and color density.
Moreover in accordance with a preferred embodiment of the present invention the method also includes scanning a medium bearing the color image.
Further in accordance with a preferred embodiment of the present invention the image includes a color image.
There is also provided in accordance with another preferred embodiment of the present invention an edge detection method including identifying a first plurality of edge pixels and a second plurality of candidate edge pixels, identifying, in parallel, all candidate edge pixels which are connected to at least one edge pixel as edge pixels, and repeating the identifying in parallel at least once.
There is also provided in accordance with another preferred embodiment of the present invention a feature labeling method in which a signal is inspected, the signal including at least one feature, the feature including a set of connected samples, the method including storing a plurality of indices for a corresponding plurality of samples, in parallel for each individual sample from among the plurality of samples, replacing the stored index of the individual sample by an index of a sample connected thereto, if the index of the connected sample is ordered above the index of the individual sample, and repeating the replacing at least once.
Further in accordance with a preferred embodiment of the present invention the replacing is repeated until only a small number of indices are replaced in each iteration.
Still further in accordance with a preferred embodiment of the present invention the signal includes an image.
Additionally in accordance with a preferred embodiment of the present invention the signal includes a color image.
There is also provided in accordance with another preferred embodiment of the present invention image correction apparatus including a transformation computer operative to compute a transformation for an output image imaged by a distorting lens which transformation compensates for the lens distortion, an in-parallel transformer operative to apply the transformation in parallel to each of a plurality of pixels in the output image.
There is also provided in accordance with another preferred embodiment of the present invention an associative memory including an array of PEs including a plurality of PEs, wherein each PE includes a processor of variable size, and a word of variable size including an associative memory cell, wherein all of the associative memory cells from among the plurality of associative memory cells included in the plurality of PE""s are arranged in the same location within the word and wherein the plurality of words included in the plurality of PE""s together form a FIFO.
Further in accordance with a preferred embodiment of the present invention the word of variable size includes more than one associative memory cell.
There is also provided in accordance with another preferred embodiment of the present invention a method for modifying contents of a multiplicity of memory cells and including performing, once, an arithmetic computation on an individual value stored in a plurality of memory cells, storing the result of the arithmetic computation in a plurality of memory cells which contain the individual value.
Further in accordance with a preferred embodiment of the present invention the storing is carried out in all memory cells in parallel.
There is also provided in accordance with another preferred embodiment of the present invention a method for constructing associative signal processing apparatus for processing an incoming signal, the method including arranging, on a module, an array of processors, each processor including a multiplicity of associative memory cells, each sample of an incoming signal being processed by at least one of the processors, arranging, on the same module, a register array including at least one register operative to store responders arriving from the processors and to provide communication between processors, and arranging, on the same module, an I/O buffer register for inputting and outputting a signal.
Further in accordance with a preferred embodiment of the present invention at least one sample is processed by two or more of the processors.
Still further in accordance with a preferred embodiment of the present invention at least one of the processors processes more than one sample.
Additionally in accordance with a preferred embodiment of the present invention the register array includes a plurality of registers.
Moreover in accordance with a preferred embodiment of the present invention the order in which the I/O buffer inputs an image differs from the row/column order of the image.
Further in accordance with a preferred embodiment of the present invention the order in which the I/O buffer inputs the samples differs from the order of the samples within the incoming signal.
Still further in accordance with a preferred embodiment of the present invention the register array includes a plurality of registers operative to store responders arriving from the processors.
Additionally in accordance with a preferred embodiment of the present invention the at least one register provides communication between the processors.
Moreover in accordance with a preferred embodiment of the present invention the at least one register provides communication between processors which are processing nonadjacent samples.
Further in accordance with a preferred embodiment of the present invention the apparatus also includes an I/O buffer register operative to input and output a signal.
Still further in accordance with a preferred embodiment of the present invention the processor array, the register array and the I/O buffer register are arranged on a single module.
Additionally in accordance with a preferred embodiment of the present invention the processor array, the register array and the I/O buffer register are arranged on a single silicon die.
Moreover in accordance with a preferred embodiment of the present invention the I/O buffer register includes a plurality of buffer register cells whose number is at least equal to the number of processors in the two-dimensional processor array.